package codetop.microsoft.T17;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author: 18362
 * @Create: 2022-08-16 22:20:06 星期二
 */
class Solution {
    private List<String> res = new ArrayList<>();
    public static final Map<Integer, String> map = new HashMap<>();
    static {
        int i = 0;
        for (int j=2; j<=9; ++j) {
            StringBuilder sb = new StringBuilder();
            for (int k=0; k<3; ++k) {
                sb.append((char) (i+'a'));
                i++;
            }
            if (j == 7 || j == 9) {
                sb.append((char) (i+'a'));
                i++;
            }
            map.put(j, sb.toString());
        }
    }

    public List<String> letterCombinations(String digits) {
        dfs(digits, 0, new StringBuilder());
        return res;
    }

    private void dfs(String digits, int cur, StringBuilder sb) {
        if (cur == digits.length()) {
            if (sb.length() > 0)
                res.add(sb.toString());
            return;
        }
        String s = map.get(digits.charAt(cur) - '0');
        for (int i=0; i<s.length(); ++i) {
            sb.append(s.charAt(i));
            dfs(digits, cur+1, sb);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}